package Hot100;

import common.TreeNode;

/**
 * @author zhangmin
 * @create 2021-12-27 10:23
 */
public class flatten114 {
    /**114. 二叉树展开为链表
     * 给你二叉树的根结点 root ，请你将它展开为一个单链表：展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
     * 展开后的单链表应该与二叉树 先序遍历 顺序相同。
     * 按照先序顺序遍历改变左右节点
     * */
    public void flatten(TreeNode root) {
        if (root==null) return;
        flatten(root.left);
        flatten(root.right);
        //将展开后的左右子树合并到root上
        TreeNode leftNode=root.left;
        TreeNode rightNode=root.right;
        root.right=leftNode;
        root.left=null;
        TreeNode p=root;
        while (p.right!=null) p=p.right;
        p.right=rightNode;
    }

}
